import java.util.Scanner;

/**
 * 功能：https://leetcode.cn/problems/merge-two-sorted-lists/
 * 作者：lc
 * 日期：2024/9/28 11:05
 */
class Algorithm_003_MergeTwoLists {
    public static ListNode_003 mergeTwoLists(ListNode_003 list1, ListNode_003 list2) {
        // 如果其中一个链表为空，则返回另一个链表
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }
        // 定义一个头节点，指向较小的节点
        ListNode_003 head = list1.val <= list2.val ? list1 : list2;
        // 定义两个指针，分别指向两个链表的下一个节点
        ListNode_003 cur1 = head.next;
        ListNode_003 cur2 = head == list1 ? list2 : list1;
        // 定义一个指针，指向当前节点的前一个节点，最初时指向给新链表头节点
        ListNode_003 pre = head;
        // 遍历两个链表，将较小的节点插入到新链表中
        while (cur2 != null && cur1 != null) {
            if (cur1.val <= cur2.val) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }
        // 将剩余的节点插入到新链表中
        pre.next = cur2 == null ? cur1 : cur2;
        // 返回新链表的头节点
        return head;
    }
}

class ListNode_003 {
    int val;
    ListNode_003 next;

    ListNode_003() {
    }

    ListNode_003(int val) {
        this.val = val;
    }

    ListNode_003(int val, ListNode_003 next) {
        this.val = val;
        this.next = next;
    }
}